package com.atguigu.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

/**
 * 逆波兰表达式
 * 从中缀表达式, 到后缀表达式, 本质上, 是对计算优先级的一种排序
 * 顺序思路考虑优先级:
 * 1. 每嵌套一层括号, 则优先级就高一大层, 这种大层超过任何默认的符号优先级, 仅有再进行内部的括号括起来才能再提升优先级.
 * 2. 其他优先级处理, 参考中缀表达式原始思路
 */
public class ReversePolandNotion {
    public static void main(String[] args) {
//        String middle="1+((2+3)*14)- 5";
//        String middle="1+6-4/2+5+6-1*3";
        String middle="7+(2*2)^2-5+11/5+3-4";
        List<String> middleList = convertFactorList(middle);
        System.out.println("middleList:"+middleList);
        List<String> suffixList = convertSuffix(middleList);
        System.out.println("suffixList:"+suffixList);

//        String s = "1 2 + 3 4 * -";
//        String s = "4 5 * 8 - 60 + 8 2 / +";
//
//        List<String> factorList = splitList(s);
//        System.out.println("list:"+factorList);
        Stack<String> stack = new Stack<>();
        for (String factor : suffixList) {
            if (factor.matches("\\d+")) {
                stack.push(factor);
            }else{
                OperateSign operateSign = new OperateSign(factor.charAt(0));
                operateSign.calc(stack);
            }
        }

        System.out.println("result:"+stack.pop());

    }

    public static List<String> splitList(String formula){
        return Arrays.stream(formula.split(" ")).filter(item-> !"".equals(item)).collect(Collectors.toList());
    }

    public static List<String> convertFactorList(String formula){
        List<String> resultList=new ArrayList<>();
        StringBuilder numCache=new StringBuilder();
        for (char c : formula.toCharArray()) {
            if (c>=48&&c<=57) {
                numCache.append(c);
            }else if(c==' '){
                // do nothing
            }else{
                if (numCache.length()>0) {
                    resultList.add(numCache.toString());
                    numCache=new StringBuilder();
                }
                resultList.add(""+c);
            }
        }
        if (numCache.length()>0) {
            resultList.add(numCache.toString());
        }
        return resultList;
    }
    public static List<String> convertSuffix(List<String> middleList){
        // 创建中转栈及队列
        Stack<String> operStack=new Stack<>();
        List<String> resultList=new ArrayList<>();

        // 分别对中缀因子集合顺序遍历
        for (String middle : middleList) {
            if (middle.matches("\\d+")) {
                resultList.add(middle);
            }else if("(".equals(middle)){
                operStack.push(middle);
            }else if(")".equals(middle)){
                while(!"(".equals(operStack.peek())){
                    resultList.add(operStack.pop());
                }
                operStack.pop();
            }else{
                if (operStack.empty()) {
                    operStack.push(middle);
                }else{
                    // 优先级比较: 仅当当前符号优先级更高时,才搁置,否则弹出
                    do{
                        String peek = operStack.peek();
                        if ("(".equals(peek)) {
//                            operStack.push(middle);
                            break;
                        }else if(new OperateSign(peek.charAt(0)).priority()<new OperateSign(middle.charAt(0)).priority()){
//                            operStack.push(middle);
                            break;
                        }else{
                            resultList.add(operStack.pop());
                        }
                    }while(!operStack.empty());
                    operStack.push(middle);
                }
            }
        }
        while(!operStack.empty()){
            resultList.add(operStack.pop());
        }

        return resultList;
    }

}


class OperateSign{
    private final char oper;

    public OperateSign(char oper) {
        this.oper = oper;
    }

    public boolean isOper(){
        return oper=='+'||oper=='-'||oper=='*'||oper=='/'||oper=='^';
    }

    public int priority(){
        switch (oper){
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '^':
                return 3;
            default:
                throw new RuntimeException("不支持的符号");
        }
    }

    public int calc(int num1,int num2){
        switch (oper){
            case '+':
                return num1+num2;
            case '-':
                return num2-num1;
            case '*':
                return num1*num2;
            case '/':
                return num2/num1;
            case '^':
                int cache=1;
                for (int i = 0; i < num1; i++) {
                    cache=cache*num2;
                }
                return cache;
            default:
                throw new RuntimeException("不支持的符号");
        }
    }

    public void calc(Stack<String> numStack){
        String num1 = numStack.pop();
        String num2 = numStack.pop();
        int result = calc(Integer.parseInt(num1), Integer.parseInt(num2));
        numStack.push(""+result);
    }
}
